package com.justnow.offer;

import java.util.Stack;

/**
 * @author justnow
 * Created on 2020-09-01
 * Description
 * leetcode-42 接雨水
 */
public class Solution17 {
    public int trap (int[] height) {
        if (height == null) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int curIndex = stack.pop();
                //如果栈顶
                while (!stack.isEmpty() && height[stack.peek()] == height[curIndex]) {
                    stack.pop();
                }
                if (!stack.isEmpty()) {
                    int stackTop = stack.peek();
                    ans += (Math.min(height[stackTop], height[i]) - height[curIndex]) * (i - stackTop - 1);
                }
            }
            stack.add(i);
        }
        return ans;
    }
}
